﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Net.Mime.MediaTypeNames;

namespace CSLearn
{
    public class Graph
    {
        int[] father;

        void InitFather()
        {
            for (int i = 0; i < father.Length; i++)
            {
                father[i] = i;
            }
        }

        int Find(int u)
        {
            if (u == father[u]) return u;
            father[u] = Find(father[u]);
            return father[u];
        }

        bool IsSame(int u, int v)
        {
            u = Find(u);
            v = Find(v);
            return u == v;
        }

        void Join(int u, int v)
        {
            u = Find(u);
            v = Find(v);
            if (u == v) return;
            father[v] = u;
        }

        // 获得移除的边(逻辑同684冗余连接)
        int[] GetRemove(int[][] edges)
        {
            father = new int[edges.Length + 1];
            InitFather();
            for (int i = 0; i < edges.Length; i++)
            {
                if (IsSame(edges[i][0], edges[i][1]))
                    return edges[i];
                Join(edges[i][0], edges[i][1]);
            }
            return null;
        }

        // 移除指定边后是否为树
        bool IsTreeAfterDel(int[][] edges, int removeIndex)
        {
            father = new int[edges.Length + 1];
            InitFather();
            for (int i = 0; i < edges.Length; i++)
            {
                if (i == removeIndex) continue;
                if (IsSame(edges[i][0], edges[i][1]))
                    return false;
                Join(edges[i][0], edges[i][1]);
            }
            return true;
        }

        /// <summary>
        /// leetcode  685  冗余连接 II
        /// </summary>
        /// <param name="edges"></param>
        /// <returns></returns>
        public int[] FindRedundantDirectedConnection(int[][] edges)
        {
            int n = edges.Length;
            // 首先统计节点的入度
            int[] inDegree = new int[n + 1];
            for (int i = 0; i < n; i++)
            {
                inDegree[edges[i][1]]++;
            }
            // 获取入度为 2 的节点对应的边
            Stack<int> twoDegree = new Stack<int>();
            for (int i = 0; i < edges.Length; i++)
            {
                if (inDegree[edges[i][1]] == 2)   twoDegree.Push(i);
            }
            // 入度为 2 的节点删去其中一条边即为结果
            if(twoDegree.Count > 0)
            {
                int index = twoDegree.Pop();
                if (IsTreeAfterDel(edges, index)) return edges[index];
                return edges[twoDegree.Pop()];
            }

            // 若无入度为 2 的节点，则删去成环的边
            return GetRemove(edges);
        }










        //int[] father;
        //void InitFather()
        //{
        //    for (int i = 0; i < father.Length; i++)
        //    {
        //        father[i] = i;
        //    }
        //}

        //int Find(int u)
        //{
        //    if (u == father[u]) return u;
        //    else
        //        father[u] = Find(father[u]);
        //    return father[u];
        //}

        //bool IsSame(int u, int v)
        //{
        //    u = Find(u);
        //    v = Find(v);
        //    return u == v;
        //}

        //void Join(int u, int v)
        //{
        //    u = Find(u);
        //    v = Find(v);
        //    if (u == v) return;
        //    father[v] = u;
        //}

        ///// <summary>
        ///// leetcode  684  冗余连接
        ///// </summary>
        ///// <param name="edges"></param>
        ///// <returns></returns>
        //public int[] FindRedundantConnection(int[][] edges)
        //{
        //    int n = edges.Length;
        //    father = new int[n + 1];
        //    InitFather();
        //    for (int i = 0; i < n; i++)
        //    {
        //        if (IsSame(edges[i][0], edges[i][1]))
        //            return edges[i];
        //        Join(edges[i][0], edges[i][1]);
        //    }
        //    return null;
        //}
        //int[] father;

        //void InitFather()
        //{
        //    for (int i = 0; i < father.Length; i++)
        //    {
        //        father[i] = i;
        //    }
        //}

        //bool IsSame(int u, int v)
        //{
        //    u = Find(u);
        //    v = Find(v);
        //    return u == v;
        //}

        //int Find(int u)
        //{
        //    //if (u == father[u]) return u;
        //    //else return father[u] = Find(father[u]); // 路径压缩
        //    return u == father[u] ? u : father[u] = Find(father[u]);
        //}

        //void Join(int u, int v)
        //{
        //    u = Find(u); // 寻找u的根
        //    v = Find(v); // 寻找v的根
        //    if (u == v) return; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
        //    father[v] = u;
        //}

        /// <summary>
        /// leetcode  1971  寻找图中是否存在路径
        /// </summary>
        /// <param name="n"></param>
        /// <param name="edges"></param>
        /// <param name="source"></param>
        /// <param name="destination"></param>
        /// <returns></returns>
        //public bool ValidPath(int n, int[][] edges, int source, int destination)
        //{
        //    father = new int[n];
        //    InitFather();
        //    for (int i = 0; i < edges.Length; i++)
        //    {
        //        Join(edges[i][0], edges[i][1]);
        //    }
        //    return IsSame(source, destination);
        //}



        /// <summary>
        /// leetcode  2316  统计无向图中无法互相到达的点对数(未完成)
        /// </summary>
        /// <param name="n"></param>
        /// <param name="edges"></param>
        /// <returns></returns>
        public long CountPairs(int n, int[][] edges)
        {
            long res = 0;


            return res;
        }

        void BFSCountPairs(int n, int[][] edges, long res)
        {
            Queue<int> queue = new Queue<int>();
            for (int i = 0; i < n; i++)
            {

            }
            for (int i = 0; i < edges.Length; i++)
            {

            }
        }


        bool[][] visited;
        int[][] move = new int[][] { new int[] { -1, 0 }, new int[] { 1, 0 }, new int[] { 0, -1 }, new int[] { 0, 1 } };

        int res = 0;
        int area = 0;
        /// <summary>
        /// leetcode  695  岛屿的最大面积(DFS)
        /// </summary>
        /// <param name="grid"></param>
        /// <returns></returns>
        public int MaxAreaOfIsland(int[][] grid)
        {
            int res = 0;
            for (int i = 0; i < grid.Length; i++)
            {
                for (int j = 0; j < grid[0].Length; j++)
                {
                    DFSMaxAreaOfIsland(grid, i, j);
                    res = Math.Max(res, area);
                    area = 0;
                }
            }
            return res;
        }

        void DFSMaxAreaOfIsland(int[][] grid, int row, int col)
        {
            if (row < 0 || row >= grid.Length || col < 0 || col >= grid[0].Length || grid[row][col] == 0)
                return;
            grid[row][col] = 0;
            area++;
            DFSMaxAreaOfIsland(grid, row - 1, col);
            DFSMaxAreaOfIsland(grid, row + 1, col);
            DFSMaxAreaOfIsland(grid, row, col - 1);
            DFSMaxAreaOfIsland(grid, row, col + 1);
        }

        /// <summary>
        /// leetcode  463  岛屿的周长
        /// </summary>
        /// <param name="grid"></param>
        /// <returns></returns>
        public int IslandPerimeter(int[][] grid)
        {
            int land = 0;
            int cover = 0;
            for (int i = 0; i < grid.Length; i++)
            {
                for (int j = 0; j < grid[0].Length; j++)
                {
                    if (grid[i][j] == 1)
                    {
                        land++;
                        if (i > 0 && grid[i - 1][j] == 1) cover++;
                        if (j > 0 && grid[i][j - 1] == 1) cover++;
                    }
                }
            }
            return 4 * land - 2 * cover;
        }

        /// <summary>
        /// leetcode  200  岛屿数量(DFS/BFS)
        /// </summary>
        /// <param name="grid"></param>
        /// <returns></returns>
        public int NumIslands(char[][] grid)
        {
            int res = 0;
            visited = new bool[grid.Length][];
            for (int i = 0; i < grid.Length; i++)
            {
                visited[i] = new bool[grid[0].Length];
            }
            for (int i = 0; i < grid.Length; i++)
            {
                for (int j = 0; j < grid[0].Length; j++)
                {
                    if (!visited[i][j] && grid[i][j] == '1')
                    {
                        res++;
                        BFSNumIslands(grid, i, j);
                    }
                }
            }
            return res;
        }

        void BFSNumIslands(char[][] grid, int row, int col)
        {
            Queue<int[]> queue = new Queue<int[]>();
            queue.Enqueue(new int[] { row, col });
            visited[row][col] = true;
            while (queue.Count > 0)
            {
                int[] cur = queue.Dequeue();
                int curRow = cur[0];
                int curCol = cur[1];
                for (int i = 0; i < 4; i++)
                {
                    int nextRow = curRow + move[i][0];
                    int nextCol = curCol + move[i][1];
                    if (nextRow < 0 || nextRow >= grid.Length || nextCol < 0 || nextCol >= grid[0].Length)
                        continue;
                    if (!visited[nextRow][nextCol] && grid[nextRow][nextCol] == '1')
                    {
                        queue.Enqueue(new int[] { nextRow, nextCol });
                        visited[nextRow][nextCol] = true;
                    }
                }
            }
        }

        void DFSNumIslands(char[][] grid, int row, int col)
        {
            if (row < 0 || row >= grid.Length || col < 0 || col >= grid[0].Length || grid[row][col] == '0')
                return;

            grid[row][col] = '0';
            DFSNumIslands(grid, row - 1, col);
            DFSNumIslands(grid, row + 1, col);
            DFSNumIslands(grid, row, col - 1);
            DFSNumIslands(grid, row, col + 1);
        }


        /// <summary>
        /// leetcode  797  所有可能的路径(图论/DFS)
        /// </summary>
        /// <param name="graph"></param>
        /// <returns></returns>
        public IList<IList<int>> AllPathsSourceTarget(int[][] graph)
        {
            IList<IList<int>> res = new List<IList<int>>();
            if (graph.Length == 0 || graph[0].Length == 0) return res;

            IList<int> path = new List<int>();
            path.Add(0);
            DFSAllPathsSourceTarget(res, path, graph, 0);
            return res;
        }

        void DFSAllPathsSourceTarget(IList<IList<int>> res, IList<int> path, int[][] graph, int cur)
        {
            if (cur == graph.Length - 1)
            {
                res.Add(new List<int>(path));
                return;
            }
            foreach (int next in graph[cur])
            {
                path.Add(next);
                DFSAllPathsSourceTarget(res, path, graph, next);
                path.Remove(next);
            }
        }
    }
}
